package datastructures.queues;

import java.util.Iterator;

/**
 * Design note
 *
 * 1. Using array data structure.
 * 2. array is used like a circular array.
 * 3. there are two references variables. One is for first index to dequeue, and the other one is for last index to enqueue
 * 4. the queue will be doubled when the queue is full.
 * 5. when the queue is empty, then the methods, first() and dequeue() will return null.
 * 6. Generic type will be used.
 *
 * @author Gatsby Lee
 *
 * @param <T>
 */
public class CircularArrayQueue<T> implements QueueADT<T> {

	private static final int DEFAULT_ARRAY_SIZE      = 100;
	private static final int RATE_TO_RESIZE_STACK    = 2;

	private T[] queue;
	private int count;
	private int dequeueIndex;
	private int enqueueIndex;

	public CircularArrayQueue() {
		this(DEFAULT_ARRAY_SIZE);
	}
	
	public CircularArrayQueue(int size) {
		this.queue = (T[])(new Object[size]);
		this.count = 0;
		this.dequeueIndex = 0;
		this.enqueueIndex = 0;
	}

	@Override
	public void enqueue(T element) {

		if (this.count == this.queue.length) {
			resizeQueue(this.queue.length * RATE_TO_RESIZE_STACK);
		}

		this.queue[this.enqueueIndex] = element;
		this.enqueueIndex = (this.enqueueIndex + 1) % this.queue.length;
		this.count++;
	}

	@Override
	public T dequeue() {
		if (this.count == 0) {
			return null;
		}

		T element  = this.queue[this.dequeueIndex];
		this.dequeueIndex = (this.dequeueIndex + 1) % this.queue.length;
		this.count--;
		return element;
	}

	@Override
	public T first() {
		return this.queue[this.dequeueIndex];
	}

	@Override
	public boolean isEmpty() {
		if (this.count == 0) {
			return true;
		}
		return false;
	}

	@Override
	public int size() {
		return this.count;
	}

	/**
	 * Resize the queue for the given size.
	 *
	 * @param size
	 */
	private void resizeQueue(int size) {
		T[] newQueue = (T[])(new Object[size]);
		for(int index=0; index < this.count; index++) {
			newQueue[index] = this.queue[this.dequeueIndex];
			this.dequeueIndex = (this.dequeueIndex + 1) % this.queue.length;
		}
		this.queue = newQueue;
		this.dequeueIndex = 0;
		this.enqueueIndex = this.count;
	}

	/**
	 * Return iterator instance
	 */
	public Iterator<T> iterator() {
		return new QueueIterator();
	}

	private class QueueIterator implements Iterator<T> {

		private int dequeueIndexForInteration = dequeueIndex;

		@Override
		public boolean hasNext() {
			if (this.dequeueIndexForInteration == enqueueIndex) {
				return false;
			}
			return true;
		}

		@Override
		public T next() {
			T element = queue[this.dequeueIndexForInteration];
			this.dequeueIndexForInteration = (this.dequeueIndexForInteration + 1) % queue.length;
			return element;
		}

		/**
		 * This functino is not supported.
		 */
		@Override
		public void remove() {}
	}
}
